//https://leetcode.cn/problems/ransom-note/submissions/
package codeRandomThoughts.Test383赎金信;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    /**
     * 重点在于magazine的每个字符只能在ransomNote中使用一次
     * 即看ransomNote是不是magazine的子集
     * 这个方法怎么这么慢???
     *
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct1(String ransomNote, String magazine) {
        Map<Character, Integer> map = new HashMap<>();
        Character ch;
        for (int i = 0; i < magazine.length(); i++) {
            ch = magazine.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }

        //遍历ransomNote,看其中的字是否都能在magazine里面找到
        for (int i = 0; i < ransomNote.length(); i++) {
            ch = ransomNote.charAt(i);
            if (!map.containsKey(ch)) {
                return false;
            } else if (map.get(ch) <= 0) {
                return false;
            }
            map.put(ch, map.getOrDefault(ch, 0) - 1);
        }
        return true;
    }

    /**
     * 优化后的算法
     * 之前慢是因为没有看题,里面明说了两个字符串中只包含小写英文字母,所以不用map
     * 建立一个长度为26的数组即可
     * 速度直接超过99.93%
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct2(String ransomNote, String magazine) {
        int[] map = new int[26];
        int ch;
        for (int i = 0; i < magazine.length(); i++) {
            ch = magazine.charAt(i) - 'a';
            map[ch]++;
        }

        //遍历ransomNote,看其中的字是否都能在magazine里面找到
        for (int i = 0; i < ransomNote.length(); i++) {
            ch = ransomNote.charAt(i) - 'a';
            if (map[ch] < 1)
                return false;
            map[ch]--;
        }
        return true;
    }
}
